package com.sicheng.algorithm.array.sorted;

import org.junit.Test;

import java.util.Arrays;

import static com.sicheng.algorithm.common.Sort.less;
import static com.sicheng.algorithm.common.Sort.swap;

/**
 * @author zsc
 * @version 1.0
 * @date 2021/9/19 21:07
 */
public class ShellSort {
    @Test
    public void insertSortTest() {
        int[] nums = {1, 0, 9, 3, 0, -2, 8};
        shellSort(nums);
        System.out.println(Arrays.toString(nums));
    }

    public void shellSort(int[] nums) {

        if (nums == null || nums.length <= 1) {
            return;
        }

        int N = nums.length;
        int h = 1;

        while (h < N / 3) {
            h = 3 * h + 1; // 1, 4, 13, 40, ...
        }

        while (h >= 1) {
            for (int i = h; i < N; i++) {
                for (int j = i; j >= h && less(nums[j], nums[j - h]); j -= h) {
                    swap(nums, j, j - h);
                }
            }
            h = h / 3;
        }
    }
}
